UVa/11844 - The Melding Plague/11844.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 map<string, long long> removeEmptyProteins(map<string, long long> &config) {
  28     map<string, long long> ans;
  29     for (map<string, long long>::iterator i = config.begin(); i != config.end(); ++i) {
  30         const string &protein = i->first;
  31         long long times = i->second;
  32         if (times > 0) {
  33             ans[protein] = times;
  34         }
  35     }
  36     return ans;
  37 }
  38
  39 map<string, long long> mutate(map<string, string> &mutations, map<string, long long> &config) {
  40     map<string, long long> ans;
  41     for (map<string, long long>::iterator i = config.begin(); i != config.end(); ++i) {
  42         const string &protein = i->first;
  43         long long times = i->second;
  44         if (mutations.count(protein) > 0) {
  45             const string &newProtein = mutations[protein];
  46             ans[  newProtein ] += times;
  47         } else {
  48             ans[  protein  ] += times;
  49         }
  50     }
  51     return ans;
  52 }
  53
  54 int solveCase(map<string, string> &mutations, const map<string, long long> &initialConfig, const map<string, long long> &finalConfig, int bound) {
  55     if (initialConfig == finalConfig) return 0;
  56
  57     map<string, long long> config = initialConfig;
  58     for (int k = 1; k <= bound; ++k) {
  59
  60         config = mutate(mutations, config);
  61         config = removeEmptyProteins(config);
  62
  63         // printf("after %d mutations config is:\n", k);
  64         // for (map<string, long long>::iterator i = config.begin(); i != config.end(); ++i) {
  65         //     const string &protein = i->first;
  66         //     long long times = i->second;
  67         //     printf("%s -> %lld\n", protein.c_str(), times);
  68         // }
  69
  70         if (config == finalConfig) return k;
  71     }
  72
  73     return -1;
  74 }
  75
  76 int main(){
  77     int NM, NI, NC, bound;
  78     while (cin >> NM >> NI >> NC >> bound) {
  79         if (NM == 0 and NI == 0 and NC == 0 and bound == 0) break;
  80
  81         bool deterministic = true;
  82         map<string, string> mutations;
  83         for (int t = 0; t < NM; ++t) {
  84             string k, v;
  85             cin >> k >> v;
  86             if (mutations.count(k) > 0 and mutations[k] != v) {
  87                  deterministic = false;
  88             }
  89             mutations[k] = v;
  90         }
  91
  92         map<string, long long> initialConfig, finalConfig;
  93         for (int i = 0; i < NI; ++i) {
  94             string protein; long long times;
  95             cin >> protein >> times;
  96             initialConfig[protein] = times;
  97         }
  98
  99         for (int i = 0; i < NC; ++i) {
 100             string protein; long long times;
 101             cin >> protein >> times;
 102             finalConfig[protein] = times;
 103         }
 104
 105         if (!deterministic) {
 106             printf("Protein mutations are not deterministic\n");
 107             continue;
 108         }
 109
 110         int ans = solveCase(mutations, initialConfig, finalConfig, bound);
 111         if (ans == -1) {
 112             printf("Nostalgia for Infinity is doomed\n");
 113         } else {
 114             printf("Cure found in %d mutation(s)\n", ans);
 115         }
 116     }
 117
 118     return 0;
 119 }